/**
 * @description: 插入排序
 * @author: 啸
 * @email: zhang_6379@sina.com
 * @date: 2021/9/9 9:32
 */
public class InsertionSort {

    public static void main(String[] args) {
        //时间复杂度为O(n^2) --> 最差的情况，从头比到尾
        //空间复杂度为O(1)
        Integer[] arr = {1,2,3,7,6,5,3};
        for (int i=0 ; i <arr.length ; i++){
            for (int j = i; j > 0; j--){
                if(arr[j].compareTo(arr[j-1])<0){
                    swap(arr,j,j-1);
                }else
                    break;
            }
        }

        for (Integer integer : arr) {
            System.out.println(integer);
        }
    }

    //换位
    public static void swap(Object[] arr, int j, int i){
        Object a = arr[j];
        arr[j] = arr[i];
        arr[i] = a;
    }
}
